#include <iostream>

using namespace std;
int max(int a, int b) {
    if (a > b) {
        return a;
    } else {
        return b;
    }
}
class Solution {
   public:
    int longestCommonSubsequence(string text1, string text2) {
        const int W = text1.size();
        const int H = text2.size();
        int** arr = (int**)malloc(sizeof(int*) * H);
        for (int i = 0; i < H; i++) {
            arr[i] = (int*)calloc(W, sizeof(int));
        }
        // 初始化
        if (text1[0] == text2[0]) {
            arr[0][0] = 1;
        }
        for (int i = 1; i < W; i++) {
            if (text1[i] == text2[0]) {
                arr[0][i] = 1;
            } else {
                arr[0][i] = arr[0][i - 1];
            }
        }
        for (int i = 1; i < H; i++) {
            if (text2[i] == text1[0]) {
                arr[i][0] = 1;
            } else {
                arr[i][0] = arr[i - 1][0];
            }
        }
        // 初始化完毕
        for (int y = 1; y < H; y++) {
            for (int x = 1; x < W; x++) {
                if (text1[x] == text2[y]) {
                    arr[y][x] = max(
                        max(arr[y][x - 1], arr[y - 1][x]),  // 邻
                        arr[y - 1][x - 1] + 1               // 左上角+1
                    );
                } else {
                    arr[y][x] = max(arr[y][x - 1], arr[y - 1][x]);
                }
            }
        }
        // for (int i = 0; i < H; i++) {
        //     for (int j = 0; j < W; j++) {
        //         cout << arr[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        return arr[H - 1][W - 1];
    }
};
int main() {
    Solution s;
    cout << s.longestCommonSubsequence("abcde", "ace");
    cout << s.longestCommonSubsequence("bsbininm", "jmjkbkjkv");
    cout << s.longestCommonSubsequence("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");
    return 0;
}
